package com.mlh.binarytree;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 缪林辉
 * @date 2024/8/26 16:26
 * @DESCRIPTION
 */
//给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
// 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
public class 路径总和3 {
    public int method1(TreeNode root, int targetSum) {
        Map<Long,Integer>map=new HashMap<>();
        map.put(0l,1);
        return recursion(root,targetSum,0l,map);
    }
    //灵茶山艾府的解法：利用前缀和
    //在二叉树上，前缀和相当于从根节点开始的路径元素和。
    // 用哈希表 map 统计前缀和的出现次数，当我们递归到节点 node 时，
    // 设从根到 node 的路径元素和为 prefixSum，那么就找到了 map[prefixSum−targetSum] 个符合要求的路径，加入答案。
    //整个递归就是前序遍历，只有前序遍历的路径才符合题目要求
    public int recursion(TreeNode node,int targetSum,long prefixSum,Map<Long,Integer> map){
        if(node==null){
            return 0;
        }
        prefixSum+=node.val;
        int res= map.getOrDefault(prefixSum-targetSum,0);
        map.merge(prefixSum, 1, Integer::sum);
        res+=recursion(node.left,targetSum,prefixSum,map);
        res+=recursion(node.right,targetSum,prefixSum,map);
        map.merge(prefixSum,-1,Integer::sum);
        return res;
    }

    public int practice(TreeNode root, int targetSum) {
        Map<Long,Integer>map=new HashMap<>();
        //初始化map
        map.put(0l,1);
        return recursionPractice(root,targetSum,0l,map);
    }

    private int recursionPractice(TreeNode node, int targetSum, Long prefixSum,Map<Long, Integer> map) {
        if(node==null){
            return 0;
        }
        prefixSum+=node.val;
        int res=map.getOrDefault(prefixSum-targetSum,0);
        map.merge(prefixSum,1,Integer::sum);
        res+=recursionPractice(node.left,targetSum,prefixSum,map);
        res+=recursionPractice(node.right,targetSum,prefixSum,map);
        map.merge(prefixSum,-1,Integer::sum);
        return res;
    }
}
